#include<stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#define  FILEIO

typedef int Type;
#define max 5

//All leaves have same depth, which is the tree's height h
//B tree degree 2t - 1 = max, t = (max + 1)/2;

typedef struct btree
{
  // The number of key inside the node.
  // n <= max
  Type n;
  /*
    x.key1<x.key2<x.key3
   */
  Type key[max];
  /*
    pointer point to child node with separated
    note: the leaf didn't have any child. so this pointer array is NULL.
   */
  struct btree* child[max + 1];
  /*
    To mark it whether it is leaf or not.
   */
  int isLeaf;
  
}*BTree,Tree;

void disk_read(BTree b)
{

}

BTree xalloc()
{
	BTree p = (BTree)malloc(sizeof(Tree));

	if(p == NULL) 
	{

		return 0;
	}
	return p;
}

BTree BTree_Search(BTree x,Type k)
{
	int i=1;
	while(i<=x->n && k>x->key[i])
		i++;

	if(i<=x->n && k==x->key[i])
		return x;

	if(x->isLeaf)
		return NULL;

	return BTree_Search(x->child[i],k);
}

void BTree_Create(BTree T)
{
	BTree x = xalloc();
	x->isLeaf = true;
	x->n=0;
	T=x;
}

int btree_main() 
{ 
#ifdef FILEIO
  freopen("btree_in.txt","r",stdin); 
  freopen("btree_out.txt","w",stdout); 
#endif
  


#ifdef FILEIO
  fclose(stdin);
  fclose(stdout);
#endif  
  
  return 0; 
}
